package com.msb.链表;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author whf
 * // 测试链接：https://leetcode.com/problems/merge-k-sorted-lists/
 * @date 2024-12-18 13:09
 */
public class _014多有序链合并使用优先级队列实现 {

    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int value) {
            val = value;
        }
    }

    // 核心关键点就是poll完了一定要加一个回去, 否则链会断掉
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 优先队列初始化，将所有非空的链表头节点加入
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(num -> num.val));
        for (ListNode list : lists) {
            if (list != null) {
                heap.add(list);
            }
        }

        // 虚拟头节点，用于简化链表拼接
        ListNode start = new ListNode(0);
        ListNode next = start;

        // 处理堆中的节点，逐个连接
        while (!heap.isEmpty()) {
            ListNode poll = heap.poll();
            next.next = poll;  // 连接到合并后的链表
            next = next.next;  // 更新链表尾部

            if (poll.next != null) {
                heap.add(poll.next);  // 将下一个节点加入堆
            }
        }

        return start.next;  // 返回合并后的链表头节点
    }
}
